package com.leetcode.partition1;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/10/8 9:28
 */
public class LC84柱状图中最大的矩形 {

    public static int largestRectangleArea(int[] heights) {
        return monotonicStack(heights);
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 4, 3};
        System.out.println(largestRectangleArea(heights));
    }

    private static int monotonicStack(int[] heights) {
        int answer = 0;
        //维护一个从栈顶到栈底是单调递减的栈
        Stack<Integer> monoStack = new Stack<>();
        //在heights的基础上首尾都添加了0
        List<Integer> heightsList = new ArrayList<>();
        heightsList.add(0);
        for (int height : heights) {
            heightsList.add(height);
        }
        heightsList.add(0);
        monoStack.push(0);
        for (int i = 1; i < heightsList.size(); i++) {
            if (heightsList.get(i) < heightsList.get(monoStack.peek())) {
                while (heightsList.get(i) < heightsList.get(monoStack.peek())) {
                    int top = monoStack.pop();
                    //计算出长和宽，并统计最大的面积
                    int width = i - monoStack.peek() - 1;
                    int height = heightsList.get(top);
                    answer = Math.max(answer, width * height);
                }
            }
            monoStack.push(i);
        }
        return answer;
    }
}
